package com.lwl.leetcode;

import org.junit.Test;

/**
 * @author lwl
 * @Description 给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：<a href="https://leetcode.cn/problems/regular-expression-matching">...</a>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2023/7/27 14:43
 */
public class Code10IsMatch {

    @Test
    public void test() {
        System.out.println(isMatch("aa", "a"));
        System.out.println(isMatch("aa", "a*"));
        System.out.println(isMatch("bbbba", ".*a*a"));
        System.out.println(isMatch("abc", "a***abc"));
        System.out.println(isMatch("ab", ".*c"));
    }

    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        if (s.contains(".") || s.contains("*")) {
            return false;
        }
        if (p.startsWith("*")) {
            return false;
        }
        if (p.contains("**")) {
            while (p.contains("**")) {
                p = p.replace("**", "*");
            }
        }
        int[][] dp = new int[s.length() + 1][p.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return process3(s.toCharArray(), 0, p.toCharArray(), 0, dp);
//        return process(s.toCharArray(), 0, p.toCharArray(), 0);
    }

    /**
     * 记忆化搜索
     */
    private boolean process3(char[] s, int index1, char[] p, int index2, int[][] dp) {
        if (index1 == s.length) {
            if (index2 == p.length) {
                dp[index1][index2] = 1;
                return true;
            }
            if (index2 + 1 < p.length && p[index2 + 1] == '*') {
                dp[index1][index2] = process3(s, index1, p, index2 + 2, dp) ? 1 : 0;
                return dp[index1][index2] == 1;
            }
            dp[index1][index2] = 0;
            return false;
        }
        if (index2 == p.length) {
            dp[index1][index2] = 0;
            return false;
        }
        boolean ans = false;
        // 后面不接着 *
        if (index2 + 1 == p.length || p[index2 + 1] != '*') {
            ans = (s[index1] == p[index2] || p[index2] == '.') && process3(s, index1 + 1, p, index2 + 1, dp);
        } else { // 后面接着 *
            // 没法匹配，* 拷贝0个
            if (s[index1] != p[index2] && p[index2] != '.') {
                ans = process3(s, index1, p, index2 + 2, dp);
            } else {
                // 这里可以选择用掉*或者不用*，可以和上面的分支合并
                ans = process3(s, index1 + 1, p, index2, dp)
                        || process3(s, index1, p, index2 + 2, dp);
            }
        }
        dp[index1][index2] = ans ? 1 : 0;
        return ans;
    }

    private boolean process2(char[] s, int index1, char[] p, int index2, int[][] dp) {

        if (dp[index1][index2] != -1) {
            return dp[index1][index2] == 1;
        }
        if (index1 == s.length) {
            if (index2 == p.length) {
                dp[index1][index2] = 1;
                return true;
            }
            if (index2 + 1 < p.length && p[index2 + 1] == '*') {
                dp[index1][index2] = process2(s, index1, p, index2 + 2, dp) ? 1 : 0;
                return dp[index1][index2] == 1;
            }
            dp[index1][index2] = 0;
            return false;
        }
        if (index2 == p.length) {
            dp[index1][index2] = 0;
            return false;
        }
        // 后面没有 '*'
        if (index2 + 1 >= p.length || p[index2 + 1] != '*') {
            dp[index1][index2] = (s[index1] == p[index2] || p[index2] == '.') && process2(s, index1 + 1, p, index2 + 1, dp) ? 1 : 0;
            return dp[index1][index2] == 1;
        }

        // 后面有'*','*'前面的字符可以变为0个或者n个
        if (p[index2] != '.' && s[index1] != p[index2]) {
            dp[index1][index2] = process2(s, index1, p, index2 + 2, dp) ? 1 : 0;
            return dp[index1][index2] == 1;
        }
        // 当前的'*'变成0个字符
        if (process2(s, index1, p, index2 + 2, dp)) {
            dp[index1][index2] = 1;
            return true;
        }

        while (index1 < s.length && (s[index1] == p[index2] || p[index2] == '.')) {
            if (process2(s, index1 + 1, p, index2 + 2, dp)) {
                dp[index1][index2] = 1;
                return true;
            }
            dp[index1][index2] = 0;
            index1++;
        }
        dp[index1][index2] = 0;
        return false;
    }

//    private boolean process(char[] s, int index1, char[] p, int index2) {
//        if (index1 == s.length) {
//            if (index2 == p.length) {
//                return true;
//            }
//            if (index2 + 1 < p.length && p[index2 + 1] == '*') {
//                return process(s, index1, p, index2 + 2);
//            }
//            return false;
//        }
//        if (index2 == p.length) {
//            return false;
//        }
//        // 后面没有 '*'
//        if (index2 + 1 >= p.length || p[index2 + 1] != '*') {
//            return (s[index1] == p[index2] || p[index2] == '.') && process(s, index1 + 1, p, index2 + 1);
//        }
//
//        // 后面有'*','*'前面的字符可以变为0个或者n个
//        if (p[index2] != '.' && s[index1] != p[index2]) {
//            return process(s, index1, p, index2 + 2);
//        }
//
//        if (process(s, index1, p, index2 + 2)) {
//            return true;
//        }
//
//        while (index1 < s.length && (s[index1] == p[index2] || p[index2] == '.')) {
//            if (process(s, index1 + 1, p, index2 + 2)) {
//                return true;
//            }
//            index1++;
//        }
//        return false;
//    }


}
